// 矩阵中的路径

// 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
// 路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。
// 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
// 例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

// [["a","b","c","e"],
// ["s","f","c","s"],
// ["a","d","e","e"]]

// 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行
// 第二个格子之后，路径不能再次进入这个格子。


//4个方向 左右上下 (0,-1) (0,1) (-1,0) (1,0)
int x[4] = {0,0,-1,1};   
int y[4] = {-1,1,0,0};
int raw = 0, col = 0;

bool dfs(char** board, int i, int j, char* word, int next, int wlen)
{
    int k, d_x = i, d_y = j, save;
    if (next == wlen) return true;
    save = board[i][j];
    board[i][j] = '\0';
    for (k = 0; k < 4; k++) {
        //下一个位置
        d_x = i + x[k]; //新的i值
        d_y = j + y[k]; //新的j值
        if (d_x >=0 && d_x < raw && d_y >= 0 && d_y < col \
            && board[d_x][d_y] == word[next])
            if (dfs(board, d_x, d_y, word, next+1, wlen)) return true;
    }
    board[i][j] = save; //不匹配时，恢复board[i][j]
    return false;
}

bool exist(char** board, int boardSize, int* boardColSize, char* word){
    int i, j;
    raw = boardSize; col = *boardColSize;
    int wlen = strlen(word);
    for (i = 0; i < raw; i++)
        for (j = 0; j < col; j++)
            if (board[i][j] == word[0]) {   //可能有不同起点
                if (dfs(board, i, j, word, 1, wlen))
                    return true;
            }
    return false;
}